package com.leetcode;

/**
 * 14. 最长公共前缀
 * 分治法
 */
public class Solution14_3 {

    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        return longestCommonPrefix(strs, 0, strs.length - 1);
    }

    private String longestCommonPrefix(String[] strs, int start, int end) {
        if (start == end) {
            return strs[start];
        }
        int mid = start + (end - start) / 2;
        String str1 = longestCommonPrefix(strs, start, mid);
        String str2 = longestCommonPrefix(strs, mid + 1, end);
        return commonPrefix(str1, str2);
    }

    private String commonPrefix(String str1, String str2) {
        int minLength = Math.min(str1.length(), str2.length());
        for (int i = 0; i < minLength; i++) {
            if (str1.charAt(i) != str2.charAt(i)) {
                return str1.substring(0, i);
            }
        }
        return str1.substring(0, minLength);
    }

}
